const COINS: [usize; 8] = [1, 2, 5, 10, 20, 30, 50, 100];

/// 实现⼀个算法，⽤于实现最⼩找零纸币数。
/// 币种含：1、2、5、10、20、30、50、100元。
/// 要求：输⼊是⾦额，输出最少的找零纸币数。
/// ⽐如输⼊24，输出最⼩找零纸币数：3(⼀张20元、两张2元)。(20)
pub fn dp_rec_mc(amount: u32) -> u32 {
    let mut dp = vec![u32::MAX; (amount + 1) as usize];
    dp[0] = 0;
    for i in 1..=amount as usize {
        for j in COINS {
            if i < j {
                break;
            }
            dp[i] = std::cmp::min(dp[i], dp[i - j] + 1);
        }
    }
    dp[amount as usize]
}
